package hah;

import com.sun.deploy.util.ArrayUtil;
import com.sun.tools.javac.util.ArrayUtils;
import org.omg.PortableServer.LIFESPAN_POLICY_ID;

import javax.jnlp.IntegrationService;
import java.lang.reflect.Array;
import java.util.*;

public class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
            this.right = right;
     }
    public boolean hasPathSum(TreeNode root, int targetSum) {
          if (root==null){
              return false;
          }
          if (root.left==null&&root.right==null){
              return root.val==targetSum;
          }
          return hasPathSum(root.left,targetSum- root.val)||
                  hasPathSum(root.right,targetSum- root.val);
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int row= matrix.length;;
        int col=matrix[0].length;
        int targetrow=-1;
        for (int i=0;i<row;i++){
            if (target>= matrix[i][0]&&target<=matrix[i][col-1]){
                targetrow=i;
                break;
            }
        }
        if (targetrow==-1){
            return false;
        }else {
            int left=0;
            int right=col-1;
            while (left<=right){
                int mid=(right+left)/2;
                if (matrix[targetrow][mid]<target){
                    left=mid+1;
                }else if (matrix[targetrow][mid]>target){
                    right=mid-1;
                }else {
                    return true;
                }
            }
        }
        return false;
    }
    public int hammingWeight(int n) {
            int count=0;
            while (n>0){
                int flag=n&1;
                if (flag==1){
                    count++;
                }
                n=n>>>1;
            }
            return count;
    }
    public int[] twoSum(int[] numbers, int target) {
            int[] res=new int[2];
            int left=0;
            int right= numbers.length-1;
            while (left<=right){
                if (numbers[left]+numbers[right]<target){
                    left++;
                }else if (numbers[left]+numbers[right]>target){
                    right--;
                }else {
                    res[0]=left+1;
                    res[1]=right+1;
                    break;
                }
            }
            return res;
    }
    public int clumsy(int N) {
        Stack<Integer> stack=new Stack<>();
        int op=1;
        stack.push(N);
        int temp=N-1;
        while (temp>0){
            if (op%4==1){
                stack.push(stack.pop()*temp);
            }
            if (op%4==2){
                stack.push(stack.pop()/temp);
            }
            if (op%4==3){
                stack.push(temp);
            }
            if (op%4==0){
                stack.push(-temp);
            }
            op++;
            temp--;
        }
        int sum=0;
        while(!stack.isEmpty()){
            sum+=stack.pop();
        }
        return sum;
    }

    private TreeNode pre=null;
    private int min=Integer.MAX_VALUE;
    public int minDiffInBST(TreeNode root) {
        findmin(root);
        return min;
    }
    public void findmin(TreeNode root){
            if (root!=null){
            findmin(root.left);
            if (pre!=null){
                min=Math.min(min, root.val- pre.val);
            }
            pre=root;
            findmin(root.right);
        }
    }
    private int sum=0;
    public int rangeSumBST(TreeNode root, int low, int high) {
            bfs(root,low,high);
            return sum;
    }
    public void bfs(TreeNode root,int low,int high){
        if (root!=null){
            rangeSumBST(root.left,low,high);
            if (root.val<=high&&root.val>=low){
                sum+= root.val;
            }
            rangeSumBST(root.right,low,high);
        }
    }

    private TreeNode prenode=null;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode hh=new TreeNode(-1);
        prenode=hh;
        bfs2(root);
        return hh.right;
    }
    public void bfs2(TreeNode root){
        if (root!=null){
            bfs2(root.left);
            prenode.right=root;
            root.left=null;
            prenode=prenode.right;
            bfs2(root.right);
        }
    }


    public static void main(String[] args) {
          int[][] arr={{1}};
        new TreeNode().searchMatrix(arr,3);
    }

  }

